1. Field of the Invention
The present invention is in the field of asynchronous state machines, also known as self-timed state machines, wherein an external clock is disallowed.
2. Description of Related Art
Nearly all digital systems built today are synchronous, where processing is done in fixed time steps regulated by a common clock signal. Synchronous design methods and tools are highly evolved, enabling large design teams to develop extremely complex chips and systems. Synchronous digital logic is a cornerstone for processors and system-on-chip devices (SOCs) that power our digital age.
Asynchronous digital circuits may play crucial niche roles in today's primarily synchronous digital systems. For example, flip-flops—the essential storage elements in synchronous systems—are small asynchronous state machines, constructed with basic logic gates and employing combinatorial feedback to hold state. While asynchronous circuits can have speed and power advantages over synchronous circuits, they are difficult to design. In synchronous state machines, the clock controls the interval between state changes; hence, the next state value is allowed to become stable before being sampled. In contrast, the timing of state changes in asynchronous state machines may be irregular, based on variable combinatorial logic delays. Furthermore, asynchronous state machines are susceptible to multi-path delays that can cause signal glitches, which in turn may cause erroneous state changes. In spite of these difficulties, asynchronous circuits may fill important roles in digital systems.
While less ubiquitous than flip-flops, asynchronous timer circuits may be used for generating clock signals, generating strobes in memory arrays and aligning signals on parallel interfaces. Basic asynchronous timer functions include clock generation, pulse generation and shaping, and time-shifting signals. Digital asynchronous timer circuits mark the passing of time by how long it takes signals to pass through a group of digital logic gates. Asynchronous timers stand in stark contrast with synchronous timers where an external reference clock is the basis for marking time. In asynchronous timers, timing intervals are a function of both fixed factors e.g. circuit structure, and variable factors e.g. manufacturing process variations, operating voltage and operating temperature. Consequently, timing characteristics of delays, pulses and clocks produced by digital asynchronous timers are imprecise and variable. Still, many applications may tolerate that imprecision and variability.
Digital delay lines, ring oscillators and asynchronous ripple counters are building blocks for traditional asynchronous timing circuits. Each building block is discussed here.
The digital delay line is a linear chain of logic gates where the amount of time it takes a signal to propagate through the gate chain constitutes a time interval. Time intervals are made programmable by segmenting the gate chains and using multiplexers to steer signals through selected segments. See FIG. 1 for an example. Digital delay lines are useful for small delays, but they may not scale well because delay is a linear function of the number of logic gates in the gate chain. Hence, implementing a long-duration time interval with a digital delay line consumes a lot of space and thus is costly.
A ring oscillator may comprise an odd number of inverting gates (i.e. NOT, NAND and/or NOR gates) connected in a circular chain as illustrated in FIG. 2. Each gate output may oscillate between zero and one. The oscillation period equals two times the propagation delay through the gate chain. Ring oscillators are well suited for high-frequency clock generation where gate chains are short. A shortcoming of ring oscillators is that the oscillation period is linearly proportional to the length of the gate chain. Long oscillation periods may require large gate chains and may be costly.
An asynchronous ripple counter may consist of a cascaded chain of toggle flip-flops as illustrated in FIG. 3. An external clock or strobe clocks the low-order counter bit. An output of the low-order bit flip-flip clocks the next higher-order bit, and so on. Asynchronous ripple counters are used as frequency dividers where the low-order bit toggles at half the frequency of the input clock and each successive higher order bit toggles at half the rate of the previous bit.
Specific reference is made to U.S. Pat. No. 7,071,751, which includes a hybrid timer circuit. That hybrid timer combines three circuit structures—a ring oscillator, an asynchronous ripple counter and a synchronous counter—as illustrated in FIG. 4 of the instant invention. The hybrid timer of U.S. Pat. No. 7,071,751 is time consuming and costly to construct owing to the disparate nature of each of its three sub-components. Furthermore, programming the hybrid timer is complicated by the need to set a different parameter for each of its three sub-components. A need exists for a low-cost self-timed timer.